﻿using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.ComponentModel;
using System.Linq;
using System.Text;

namespace CollectionExtensions
{
    /// <summary>
    /// An ObservableCollection that is always sorted. Any attempt to disrupt sorting will be met with
    /// an exception.
    /// </summary>
    /// <typeparam name="T">The type of item this collection holds</typeparam>
    public class SortingObservableCollection<T> : SortingObservableCollection<T, T>
        where T : class, INotifyPropertyChanged
    {
        /// <summary>
        /// Creates a new sorted observable collection that sorts based on the given comparer.
        /// </summary>
        /// <param name="comparer">Should be of the base type</param>
        public SortingObservableCollection(IComparer<T> comparer)
            : base(comparer, i => i)
        { }
    }

    /// <summary>
    /// An ObservableCollection that is always sorted. Any attempt to disrupt sorting will be met with
    /// an exception. It watches member objects for property changes, automatically maintaining sort order.
    /// </summary>
    /// <typeparam name="T">The Type of object this collection holds. Must implement INotifyPropertyChanged</typeparam>
    /// <typeparam name="TKey">The Type of the object property that this collection should sort on (string property, int property, etc)</typeparam>
    public class SortingObservableCollection<T, TKey> : ObservableCollection<T>
        where T : class, INotifyPropertyChanged
    {
        #region Private fields

        /// <summary>
        /// Something to perform comparisons with.
        /// </summary>
        private IComparer<TKey> comparer;

        /// <summary>
        /// A function that, given an object, can pull out a key from that object for comparison.
        /// </summary>
        private Func<T, TKey> keySelector;

        #endregion

        #region Public properties

        /// <summary>
        /// Get the item associated with the specified index.
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        /// <exception cref="NotSupportedException">Thrown if you try to set a value</exception>
        public new T this[int index]
        {
            get { return base[index]; }
            set { throw new NotSupportedException("Cannot directly modify an index in a sorted collection."); }
        }

        #endregion

        #region Constructors

        /// <summary>
        /// Creates a new observable collection that will always be sorted.
        /// </summary>
        /// <param name="comparer">Should either be able to compare the base type or the type given in the selector</param>
        /// <param name="keySelector">A function to select a property of the base type for comparison</param>
        public SortingObservableCollection(IComparer<TKey> comparer, Func<T, TKey> keySelector)
        {
            this.comparer = comparer;
            this.keySelector = keySelector;
        }

        #endregion

        #region Public methods

        /// <summary>
        /// Not supported, this would potentially disrupt sort order.
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        public new void Insert(int index, T item)
        {
            throw new NotSupportedException("Cannot directly insert into an ordered list, as it would potentially break the order");
        }

        /// <summary>
        /// Not supported, this would potentially disrupt sort order.
        /// </summary>
        /// <param name="oldIndex"></param>
        /// <param name="newIndex"></param>
        public new void Move(int oldIndex, int newIndex)
        {
            throw new NotSupportedException("Cannot alter the order of the list");
        }

        /// <summary>
        /// Add the item at the appropriate location in the sorted collection.
        /// </summary>
        /// <param name="item"></param>
        public new void Add(T item)
        {
            int index = SearchForIndex(this, item);
            base.Insert(index, item);

            item.PropertyChanged += item_PropertyChanged;
        }

        /// <summary>
        /// Clears the collection of items.
        /// </summary>
        public new void Clear()
        {
            foreach (T item in this)
            {
                item.PropertyChanged -= item_PropertyChanged;
            }

            base.Clear();
        }

        /// <summary>
        /// Removes the given item.
        /// </summary>
        /// <param name="item"></param>
        /// <returns>True if removed, false if else</returns>
        public new bool Remove(T item)
        {
            item.PropertyChanged -= item_PropertyChanged;

            return base.Remove(item);
        }

        /// <summary>
        /// Removes the item at the given index.
        /// </summary>
        /// <param name="index"></param>
        public new void RemoveAt(int index)
        {
            T item = this[index];
            item.PropertyChanged -= item_PropertyChanged;

            base.RemoveAt(index);
        }

        #endregion

        #region Private event handlers

        private void item_PropertyChanged(object sender, PropertyChangedEventArgs e)
        {
            T item = sender as T;
            int currentIndex = this.IndexOf(item);

            if (Count > 1 && // not a single item list AND
                ((currentIndex > 0 && Compare(item, this[currentIndex - 1]) < 0) || // item should be before previous item OR
                (currentIndex < Count - 1 && Compare(item, this[currentIndex + 1]) > 0))) // item should be after next item
            {
                List<T> tempList = this.ToList();
                tempList.RemoveAt(currentIndex);

                int index = SearchForIndex(tempList, item);

                if (currentIndex != index)
                {
                    base.MoveItem(currentIndex, index);
                }
            }
        }

        #endregion

        #region Private helpers

        /// <summary>
        /// Compare two items using the given comparer and the key selector.
        /// </summary>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        private int Compare(T x, T y)
        {
            return comparer.Compare(keySelector(x), keySelector(y));
        }

        /// <summary>
        /// Given an item not in the collection, find what index it should be at.
        /// </summary>
        /// <param name="items"></param>
        /// <param name="item"></param>
        /// <returns>The correct index to maintain sort order</returns>
        private int SearchForIndex(IList<T> items, T item)
        {
            // Create a list of only the keys we're interested in
            List<TKey> list = new List<TKey>();

            foreach (T s in items)
            {
                list.Add(keySelector(s));
            }

            int index = list.BinarySearch(keySelector(item), comparer);

            if (index >= 0)
            {
                // Similar item exists, find a place for it
                do
                {
                    index++;
                }
                while (index < list.Count && comparer.Compare(list[index], keySelector(item)) == 0);
            }
            else
            {
                // Item does not exist
                index = ~index;
            }

            return index;
        }

        #endregion
    }
}
